The present invention relates to the field of programmable devices, and the systems and methods for programming the same. Programmable devices, such as FPGAs, typically includes thousands of programmable logic cells that use combinations of logic gates and/or look-up tables to perform a logic operation. Programmable devices also include a number of functional blocks having specialized logic devices adapted to specific logic operations, such as adders, multiply and accumulate circuits, phase-locked loops, and one or more embedded memory array blocks. The logic cells and functional blocks are interconnected with a configurable switching circuit. The configurable switching circuit selectively routes connections between the logic cells and functional blocks. By configuring the combination of logic cells, functional blocks, and the switching circuit, a programmable device can be adapted to perform virtually any type of information processing function.
The process of determining the configuration of a programmable device from a user-specified design is referred to as compilation. Typical compilation processes start with an extraction phase, followed by a logic synthesis phase, a clustering and placement phase, a routing phase, and an assembly phase. The extraction phase takes a user design, typically expressed as a netlist in a hardware description language such as Verilog or VHDL, and produces a set of logic gates implementing the user design. In the logic synthesis phase, the set of logic gates is permuted over the hardware architecture of the programmable device in order to match elements of the user design with corresponding portions of the programmable device.
Compilation software applications often must optimize a user design to match the architectural characteristics of the programmable device. These optimizations often change portions of the user design into functionally-equivalent circuits that are better suited for implementation by the programmable device. Compilation software applications may also optimize the user design to increase the operating speed, decrease the number of logic gates and other hardware resources required by the design, and/or decrease the power consumption.
For example, a logic cell of a programmable device may have a predetermined number of inputs. This allows the logic cell to potentially implement a Boolean function having up to that number of inputs. For a function with more inputs than are available in a single logic cell, the function must be split into sub-functions implemented by multiple logic cells. There are numerous techniques for manipulating designs to match hardware architectures and optimize performance.
Functional factoring is one approach to manipulating functions in designs to match hardware architectures and optimize performance. Functional factoring manipulates a truth table or binary decision diagram (BDD) representing a function to re-express the function as a combination of smaller functions.
Functional factoring is often extremely time-consuming, with complex functions taking days or even weeks of computational time to solve. Part of the reason for this is that functional factoring must separately analyze every possible factorization of a function to determine an optimal factorization of the function. Thus, as the number of function inputs increase, the number of possible factorizations considered increases exponentially. Additionally, complex functions often have a truth table or BDD representation too large to fit into most conventional processor caches. Because of this, functional factoring algorithms often incur frequent cache misses as they access a function's truth table or BDD, further increasing computation time.
Moreover, functional factoring algorithms typically factor one function at a time. In some cases, an optimal factorization of a first function may be adversely impact the factorization of a second related function. Conversely, sub-optimal factorizations of two or more separate functions may be optimal for the entire design due to the ability to share one or more sub-functions between the functions. Prior functional factoring algorithms cannot find an optimal factorization of the combination of two or more functions.
It is therefore desirable for a system and method to perform functional factoring in substantially less time than prior techniques. It is also desirable for the system and method to enable optimal factorization of the combination of two or more functions. It is further desirable for the system and method to be implemented with little or no additional cost over typical design development systems.